This invention relates to decoding operations performed upon channel coded data and, more particularly, to decoders which operate upon trellis diagrams.
Communication between systems is possible whenever a common channel connects the systems. Whether by network cables, telephone lines, or Internet Protocol sockets, the data communicated between entities travels through a channel medium.
Unfortunately, “noise” and “interference” in the channel medium may corrupt the data during transmission. Factors such as the length of the channel medium, the amount of data transmitted, the presence of spurious signals in the channel, and other environmental conditions may affect the amount of noise and interference and, thus, the quality of the received data.
The phenomena of noise and interference in a channel are so expected that the data is almost always encoded before being transmitted. A data encoder is generally made up of discrete logic such as flip-flops and NAND gates. The data encoder receives a stream of data bits, known as information bits, that are to be transmitted through a channel medium and generates additional bits, known as parity bits, based upon the information bits themselves. Together, the information bits and the parity bits make up an encoded bit stream.
This carefully designed redundant information is known as forward error correction (FEC) or channel coding. Once constructed, the encoded bit stream is transmitted across the channel. In some cases, the encoded bit stream may be modulated prior to transmission.
Upon transmission over the channel and subsequent demodulation at the receiver, some of the ‘1’ bits (or a modulated representation thereof) may be corrupted such that they are received as ‘0’ bits. Likewise, some of the ‘0’ bits may be received as ‘1’ bits. In modern digital wireless receivers, the demodulator may also report bit-by-bit “reliability metrics.” Clearly received 1's and 0's produce a high reliability metric, while ambiguously received data produces a low reliability metric. The information bits or the parity bits of the encoded bit stream, or both, may be corrupted during transmission.
In addition to the demodulator, the receiving entity includes a decoder whose purpose is to determine the information bits most likely to have been transmitted, using the demodulator outputs and knowledge of the structure of the encoder. The bit reliability metric described above can significantly enhance the capability of the decoder. As expected, the decoder may be considerably more complex than the encoder.
Shannon's celebrated Channel Coding Theorem is the inspiration for the drive towards more and more complex coded digital communications systems. Shannon's theorem states that as long the information rate (transmitted information bits per second) does not exceed the Channel Capacity, then it is possible to design FEC coding systems with arbitrarily small decoding error probability.
Shannon's theorem, however, is an asymptotic result. It actually tells us little about how to design practical coding systems—only that perfect decoding is approachable as the coding block size (number of information bits) and code complexity tends to infinity. It turns out that very powerful, hence complex, codes are easy to construct.
The difficult task, then, is to find an efficient decoding algorithm for these complex codes. Thus, the practical task of FEC code design is to find families of powerful (hence, complex) codes having specific structure that can be exploited to obtain a decoder of practical implementation complexity. Of course, as digital technology marches forward, more and more complex decoders become possible.
Some decoding algorithms operate upon specialized state diagrams, known as trellis diagrams, to produce a decoded output. A trellis diagram is a state machine that demonstrates possible state transitions of an encoder over time. Trellis diagrams describe all the possible states of the encoder, at each point in time. Many decoding algorithms use trellis diagrams, along with the channel bit stream, to arrive at the correct information bits.
The volume of calculations involved with trellis-type decoding, however, can be staggering. Accordingly, decoders may be implemented with application-specific integrated circuits (ASICs) which perform specialized trellis operations, such as butterfly operations, very efficiently. Because of the complexity of the various decoder algorithms, such ASICs may typically be designed for a single algorithm.
Other decoders may include general-purpose digital signal processors (DSPs), which may or may not include special instructions for performing trellis operations. These decoders may be programmable such that different decoding algorithms may be implemented, as needed. Such decoders may be more flexible, but may decode channel data at a slower rate than the ASIC-based decoders.
Thus, there is a continuing need for a programmable processor that may be used with a general-purpose digital signal processor for performing trellis-based decoding operations.